package org.nowcoder.leetcode.arrays;

/**
 * Title  : 149. Max Points on a Line
 * Source : https://leetcode.cn/problems/max-points-on-a-line/?envType=study-plan-v2&envId=top-interview-150
 * Author : XrazYang
 * Date   : 2023-08-10
 */
public class LeetCode_149 {
    public int maxPoints(int[][] points) {
        int max = 2;
        //边界条件
        if (points.length == 1 || points.length == 2) {
            return points.length;
        }
        //暴力解法： 三重循环,居然ac ...
        for (int i = 0; i < points.length - 2; i++) {
            int x1 = points[i][0];
            int y1 = points[i][1];
            for (int j = i + 1; j < points.length - 1; j++) {
                int x2 = points[j][0];
                int y2 = points[j][1];
                int count = 2;
                for (int l = j + 1; l < points.length; l++) {
                    int x = points[l][0];
                    int y = points[l][1];
                    //两点式判断是否在一条直线上
                    boolean flag = ((y - y2) * (x1 - x2)) == ((y1 - y2) * (x - x2));
                    if (flag) {
                        count++;
                    }
                }
                max = Math.max(max, count);
            }
        }
        return max;
    }
}
